<!--
 * @Author: your name
 * @Date: 2021-12-02 08:55:04
 * @LastEditTime: 2021-12-02 13:51:13
 * @LastEditors: Please set LastEditors
 * @Description: 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 https://zhuanlan.zhihu.com/p/109979290
 * @FilePath: \front-end-algorithm\算法\二叉树便利操作.html
-->
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>二叉树便利操作</title>
</head>

<body>

    <script>
        class Node {
            constructor(data, leftTree, rightTree) {
                this.data = data;
                this.leftTree = leftTree;
                this.rightTree = rightTree;
                this.count = 1;
            }
        }

        class BaseTree {
            constructor() {
                this.root = null;
            }

            //删除一个节点
            _removeNode(node, data) {
                if (node == null) {
                    return null;
                }
                if (data == node.data) {
                    //叶子节点
                    if (node.leftTree == null && node.rightTree == null) {
                        return null;
                    }

                    //没有右节点的节点
                    if (node.rightTree == null) {
                        return node.leftTree;
                    }

                    //有两个节点的节点
                    /**
                     * 做法：找到待删除节点的右子树上的最小值创建一个临时节点
                     * 将临时节点上的值复制到待删除节点，然后再删除临时节点
                     * 
                     * **/
                    //寻找右边子树的最小值

                    let tempNode = this.getMinNode(node.rightTree);
                    node.data = tempNode.data;
                    node.rightTree = this._removeNode(node.rightTree, tempNode.data);

                    return node;
                } else if (data < node.data) {
                    node.leftTree = this._removeNode(node.leftTree, data);
                    return node;
                } else {
                    node.rightTree = this._removeNode(node.rightTree, data);
                    return node;
                }
            }
            //删除指定节点
            remove(data) {
                this.root = this._removeNode(this.root, data)
            }
            //向二叉树插入节点
            insert(data) {
                //
                let newNode = new Node(data, null, null);
                if (this.root == null) {
                    this.root = newNode;

                } else {
                    let currentNode = this.root;
                    let parentNode = null;
                    while (true) {
                        parentNode = currentNode;
                        if (newNode.data < currentNode.data) {
                            currentNode = currentNode.leftTree;
                            if (!currentNode) {
                                parentNode.leftTree = newNode;
                                break;
                            }
                        } else if (newNode.data > currentNode.data) {
                            currentNode = currentNode.rightTree;
                            if (!currentNode) {
                                parentNode.rightTree = newNode;
                                break;
                            }
                        } else if (newNode.data == currentNode.data) {

                            // 如果给定的数据再次出现，就更新计数值
                            currentNode.count++;
                            break;
                        }
                    }
                }
            }
            //寻找给定数据节点
            find(data) {
                let currentNode = this.root;
                while (currentNode) {
                    if (currentNode.data == data) {
                        return currentNode
                    } else if (currentNode.data = data) {
                        currentNode = currentNode.leftTree;
                    } else if (currentNode.data < data) {
                        currentNode = currentNode.rightTree;
                    }
                }
                return null;
            }
            //获得最小值节点
            getMinNode(node = this.root) {
                let currentNode = node;
                while (currentNode.leftTree) {
                    currentNode = currentNode.leftTree;
                }
                return currentNode;
            }
            //获取最大值节点
            getMaxNode(node = this.root) {
                let currentNode = node;
                while (currentNode.rightTree) {
                    currentNode = currentNode.rightTree;
                }
                return currentNode;
            }
            //中序递归遍历
            inOrderRec(node = this.root) {
                //递归方法遍历二叉树
                let result = '';
                if (node) {
                    result += this.inOrderRec(node.leftTree);//中序遍历左子树
                    result += `${node.data} `;//访问根节点
                    result += this.inOrderRec(node.rightTree);//中序遍历右子树
                }
                return result;

            }
            //中序非递归遍历
            inOrderNonRec(node = this.root) {
                //中间栈
                let stack = [];
                let result = '';
                while (node || stack.length) {
                    if (node) {
                        stack.push(node);//进栈
                        node = node.leftTree;//扫描该节点的所有左子节点
                    } else {
                        node = stack.pop();//进栈一个节点
                        result += `${node.data} `;//访问该节点
                        node = node.rightTree;//扫描该节点的右边子节点
                    }
                }
                return result;
            }
            //前序递归遍历
            preOrderRec(node = this.root) {
                // 如果二叉树是空，直接返回，否则会有三种情况
                // 1、访问根节点
                // 2、前序遍历左子树
                // 3、前序遍历右子树
                let result = '';
                if (!(node == null)) {
                    result += `${node.data} `;//访问根节点
                    result += this.preOrderRec(node.leftTree);//遍历前序左子树
                    result += this.preOrderRec(node.rightTree);//遍历前序右边子树
                }
                return result;
            }
            //前序非递归遍历
            preOrderNonRec(node = this.root) {
                let stack = []; // 栈
                let result = '';
                while (node || stack.length) {
                    if (node) {
                        result += `${node.data} `;
                        stack.push(node);
                        node = node.leftTree;
                    } else {
                        node = stack.pop();
                        node = node.rightTree;
                    }
                }

                return result;
            }

            // 后序遍历的操作过程
            //   如果根节点为空直接返回，
            // 后序遍历左子树
            // 后序遍历右子树
            // 访问根节点
            //后序递归遍历
            postOrderRec(node = this.root) {
                let result = '';
                if (!(node == null)) {
                    result += this.postOrderRec(node.leftTree); //后序遍历左子树
                    result += this.postOrderRec(node.rightTree);//后序遍历右子树
                    result += `${node.data} `;// 访问根节点
                }
                return result;
            }
            //后序非递归遍历
            /* 后序遍历的非递归算法比较复杂，因为后序非递归遍历二叉树的顺序是先访问左子树，再访问右子树，最后访问根节点。
            当用堆栈来存储节点，必须分清楚返回根节点时，是从左子树返回的，还是从右子树返回的。
            所以使用辅助指针ret，其指向最近访问过的节点。
            当访问一个节点时，栈中的节点恰好是该节点的所有祖先。从栈底到栈顶节点在加上该节点，
            刚好构成从根节点到该节点的一条路径。 */
            postOrderNonRec(node = this.root) {
                let stack = [];
                let ret = node;
                let result = '';
                while (node || stack.length) {
                    if (node) {
                        stack.push(node);
                        node = node.leftTree;
                    } else {
                        node = stack[stack.length - 1];
                        if (node.rightTree && node.rightTree != ret) {
                            node = node.rightTree;
                            stack.push(node);
                            node = node.leftTree;
                        } else {
                            node = stack.pop();
                            result += `${node.data} `;
                            ret = node;
                            node = null;
                        }
                    }
                }

                return result;
            }
            //层次遍历
            levelOrder(node = this.root) {
                let queue = [];
                let result = '';
                queue.push(node);//根节点入队
                while (queue.length) {
                    node = queue.shift();//出队
                    result += `${node.data} `;
                    if (node.leftTree) {
                        queue.push(node.leftTree);
                    }
                    if (node.rightTree) {
                        queue.push(node.rightTree);
                    }
                }
                return result;
            }
            //知道二叉树的先序和中序排序，重建二叉树
            //道理---------------
            /*  知道二叉树的先序和中序排列，让你重建一颗这样的二叉树出来。下面来搞定它。
                由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树，在先序遍历序列中，第一个结点一定是二叉树的根结点，而在中序遍历中，根结点必然将中序序列分割成两个子序列，前一个子序列就是根结点的左子树的中序序列，后一个子序列是根结点的右子树的中序序列。根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。如此递归地进行下去，便能唯一地确定这棵二叉树
                同理，由二叉树的后序序列和中序序列也可以唯一地确定一棵二又树，因为后序序列的最后个结点就如同先序序列的第一个结点，可以将中序序列分割成两个子序列，然后采用类似的方法递归地进行划分，就可以得到一棵二叉树。 */
            /**
             *
             *  @params { Array } preArr 先序序列 
             *  @params { Array } inArr 中序序列
             *  @params { Number } pBeg 先序序列前一个标识
             *  @params { Number } pEnd 先序序列最后一个下标
             *  @params { Number } iBeg 中序序列前一个标识
             *  @params { Number } iEnd 中序序列最一个标识
             * 
             */
            preInCreate(preArr, inArr, pBeg, pEnd, iBeg, iEnd) {

                let lLen = 0, rLen = 0;
                let splitIdx = -1;
                let node = new Node(preArr[pBeg], null, null);//根节点
                if (!this.root) {
                    this.root = node;
                }
                for (let i = iBeg; i < iEnd; i++) {
                    if (inArr[i] == preArr[pBeg]) {
                        splitIdx = i;
                        break;
                    }
                }

                if (splitIdx > -1) {
                    lLen = splitIdx - iBeg;
                    rLen = iEnd - splitIdx;
                }

                if (lLen) {
                    node.leftTree = this.preInCreate(preArr, inArr, pBeg + 1, PBeg + lLen, iBeg + lLen - 1)
                } else {
                    node.leftTree = null;
                }

                if (rLen) {
                    node.rightTree = this.preInCreate(preArr, inArr, pEnd - rLen + 1, pENd, iEnd - rLen + 1, iEnd);
                } else {
                    node.rightTree = null;
                }
                return node;
            }

        }

        let myTree = new BaseTree();
        myTree.insert(20);
        myTree.insert(13);
        myTree.insert(7);
        myTree.insert(9);
        myTree.insert(15);
        myTree.insert(14);
        myTree.insert(42);
        myTree.insert(22);
        myTree.insert(21);
        myTree.insert(24);
        myTree.insert(57);
        console.log(myTree.levelOrder());

        console.log(myTree.preOrderRec());
        console.log(myTree.preOrderNonRec());


        console.log(myTree.inOrderRec());
        console.log(myTree.inOrderNonRec());


        console.log(myTree.postOrderRec());
        console.log(myTree.postOrderNonRec());

    </script>

</body>

</html>